package com.lfg.leetcode.leetcode0;


public class No53maxSubArray {

    public static void main(String[] args) {
        int ret = maxSubArray(new int[]{8, -1, -1, -1, -1, -1, -1, 10});
        System.out.println(ret);
    }

    public static int maxSubArray(int[] nums) {
        int ret = 0;
        if (nums.length == 0) {
            return ret;
        }
        int length = nums.length - 1;
        ret = nums[0];
        int sum = ret;
        for (int i = 1; i <= length; i++) {
            if (sum > 0) {
                sum += nums[i];
            } else {
                sum = nums[i];
            }
            ret = Math.max(sum, ret);
        }
        return ret;
    }

    public static int maxSubArray2(int[] nums) {
        int sum = nums[0];
        int n = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (n > 0) n += nums[i];
            else n = nums[i];
            sum = Math.max(sum, n);
        }
        return sum;
    }
}

